import java.util.*;

public class Leet301II {
    public static void main(String[] args) {
        Leet301II l = new Leet301II();
        System.out.println(l.removeInvalidParentheses(")("));
    }
    public List<String> removeInvalidParentheses(String s) {
        Queue<String> queue = new ArrayDeque<>();
        queue.add(s);
        Set<String> set = new HashSet<>();
        int min = 0;
        while (!queue.isEmpty()){
            String str = queue.remove();
            if (check(str)){
                set.add(str);
                min = str.length();
                continue;
            }
            if (str.length()<min)
                continue;
            else {
                for (int i = 0; i < str.length(); i++) {
                    if (str.charAt(i)=='('||str.charAt(i)==')'){
                        queue.add(str.substring(0,i)+str.substring(i+1));
                    }

                }
            }
        }
        return new ArrayList<>(set);
    }
    boolean check(String s){
        char[] chs = s.toCharArray();
        int l = 0;
        for (char ch : chs) {
            if (ch=='(')
                l++;
            else if (ch==')')
                l--;
            if (l<0)
                return false;
        }
        return l == 0;
    }
}
